package my.algorithms;

import my.datastructures.TreeNode;


public class BinaryTree
{
    public static void preOrder(TreeNode node)
    {
        System.out.println(node.value);
        if (node.left != null)
        {
            preOrder(node.left);
        }
        if (node.right != null)
        {
            preOrder(node.right);
        }
    }

    public static void postOrder(TreeNode node)
    {
        if (node.left != null)
        {
            preOrder(node.left);
        }
        if (node.right != null)
        {
            preOrder(node.right);
        }
        System.out.println(node.value);
    }

    public static void inOrder(TreeNode node)
    {
        if (node.left != null)
        {
            preOrder(node.left);
        }
        System.out.println(node.value);
        if (node.right != null)
        {
            preOrder(node.right);
        }
    }

    public static void ReverseTree(TreeNode node)
    {
        if (node != null)
        {
            TreeNode tmpNode = node.right;
            ReverseTree(node.left);
            ReverseTree(node.right);
            node.right = node.left;
            node.left = tmpNode;
        }

    }


    /**
     * This gets the distance between the two longest nodes on the left and right of the tree, aka diameter
     *
     * @param node
     * @return
     */
    public static int getDiameter(TreeNode node)
    {
        if (node == null)
        {
            return 0;
        }

        int leftHeight = maxDepth(node.left);
        int rightHeight = maxDepth(node.right);

        int leftDiameter = getDiameter(node.left);
        int rightDiameter = getDiameter(node.right);

        return Math.max(leftHeight + rightHeight + 1,
                Math.max(leftDiameter, rightDiameter));
    }


    /**
     * This could also be thought of as the height of the tree
     *
     * @param n
     * @return
     */
    public static int maxDepth(TreeNode n)
    {
        if (n == null)
        {
            return 0;
        }

        return 1 + Math.max(maxDepth(n.left), maxDepth(n.right));
    }

    /**
     * This could also be thought of as the height of the tree
     *
     * @param n
     * @return
     */
    public static int maxDepthValue(TreeNode n)
    {
        class MaxValue
        {
            int maxDepth = 0;
            int maxValue = -1;
            void findMax(TreeNode n, int depth)
            {
                if (n == null)
                {
                    return;
                }
                if(n.left != null)
                {
                    findMax(n.left, depth + 1);
                }
                if (n.right != null)
                {
                    findMax(n.right, depth + 1);
                }

                if (n.right == null && n.left == null)
                {
                    if (depth > maxDepth)
                    {
                        maxDepth = depth;
                        maxValue = n.value;
                    }
                }
            }
        }
        MaxValue finder = new MaxValue();
        finder.findMax(n, 0);
        return finder.maxValue;
    }


    public static void main(String[] args)
    {
        /*                     5
         *                   /  \
         *                  6    7
         *                / \     \
         *               8  9     10
         *                       /
         *                      11
         *                        \
         *                        12
         * Max Depth: 5
         * Diameter: 7
         */
        TreeNode node = new TreeNode(5);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(7);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(9);
        TreeNode node5 = new TreeNode(10);
        TreeNode node6 = new TreeNode(11);
        TreeNode node7 = new TreeNode(12);

        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        node5.left = node6;
        node6.right = node7;

        // System.out.println(diameter(node));
        System.out.println("Max Depth: " + maxDepth(node));
        System.out.println("Diameter: " + getDiameter(node));
        System.out.println("Max Value: " + maxDepthValue(node));
    }


}
